

package niuke.zonghe;
import java.util.Scanner;
/**
 * @author liyuhui
 * @date {DATE}
 * @description
 */
public class Maze {
    /**
     * 输入两个整数，分别表示二位数组的行数，列数。
     * 再输入相应的数组，其中的1表示墙壁，0表示可以走的路。
     * 数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
     * 左上角到右下角的最短路径，格式如样例所示。
     */

    public static void main(String[] args) {
        //初始化迷宫
        Scanner s = new Scanner(System.in);
        String q=s.nextLine();
        String[] q1=q.split(" ");
        int N=Integer.valueOf(q1[0]);
        int M=Integer.valueOf(q1[1]);
        int[][] arr=new int[N][M];

        for (int i=0;i<N;i++){
            String w=s.nextLine();
            String[] r=w.split(" ");
            for (int j=0;j<r.length;j++){
                arr[i][j]=Integer.valueOf(r[j]);
            }
        }

//        int[][] arr = {{0,1,0,0,0},{0,1,0,1,0},{0,0,0,0,0},{0,1,1,1,0},{0,0,0,1,0}};
//        int N = 5;
//        int M = 5;

//        int[][] arr = {{0,1,1},{0,0,0},{1,1,0}};
//        int N = 3;
//        int M = 3;

        boolean[][] b = new boolean[N][M];
        b[N-1][M-1]=true;

        hasPath(arr, b, 0, 0, N, M);

        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                if (b[i][j]) {
                    System.out.println("("+i+","+j+")");
                }
            }
        }

    }

    private static boolean hasPath(int[][] arr, boolean[][] b, int n , int m, int N, int M) {
        if(m>=M || n>=N || m<0 || n<0 || arr[n][m]==1) {
            return false;
        }

        boolean flag = false;

        if (n==N-2 && m==M-1 && arr[n][m]==0){
            b[n][m]=true;
            return true;
        }else if (m==M-2 && n==N-1 && arr[n][m]==0) {
            b[n][m]=true;
            return true;
        }else if (arr[n][m]==0&&!b[n][m]) {//没有被访问过，且可以被访问
            b[n][m] = true;
            flag = hasPath(arr, b, n+1, m, N, M) || hasPath(arr, b, n, m+1, N, M) || hasPath(arr, b, n-1, m, N, M) || hasPath(arr, b, n+1, m, N, M);
        }

        if (flag) {
            return flag;
        }else {
            b[n][m] = false;
            return false;
        }

    }
}
